/*
	parity.cc	Parity Calculation
	Copyright (c) 2003, 2004 Kriang Lerdsuwanakij
	email:		lerdsuwa@users.sourceforge.net

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "parity.h"
#include "order.h"
#include "iter.h"

#include <iostream>

// FIXME: Iterator data are shared and not thread-safe.

struct parity_data {
	int x;
	int y;
	int area;
};

const bool DEBUG_PARITY = false;

int	parity_eval_alpha_beta(search_info &info, int player)
{
	parity_data data[NUM_MOVE];
	parity_data *ptr[NUM_MOVE];
	int count[NUM_MOVE/4];	// Max number of area possible
	int num_data = 0;

	if (info.board->get_num_move() == 0 || info.board->get_num_move() == NUM_MOVE)
		return 0;

	bool even_move_left = true;
	if (info.board->get_num_move() & 1)
		even_move_left = false;

				// Obtain a list of empty squares
	board_endgame_iterator iter(info.empties);
	iter.init_pos();
	do {
		int pos = iter.pos;
		data[num_data].x = pos_to_x(pos);
		data[num_data].y = pos_to_y(pos);
		data[num_data].area = -1;
		ptr[num_data] = &data[num_data];
		num_data++;
	} while (iter.next());

	for (int i = 0; i < NUM_MOVE/4; ++i)
		count[i] = 0;

				// Separate empties into different
				// areas
	int cur_area = 0;
	int cur_done = 0;
	for (int i = 0; i < num_data; ++i) {

				// Not previously assigned number
		if(ptr[i]->area == -1) {
				// New area
			ptr[i]->area = cur_area;
			cur_area++;
		}
				// Look for neighbor empties
		for (int j = cur_done+1; j < num_data; ++j) {
			int xdiff = ptr[j]->x - ptr[i]->x;
			if (xdiff >= -1 && xdiff <= 1) {
				int ydiff = ptr[j]->y - ptr[i]->y;
				if (ydiff >= -1 && ydiff <= 1) {
							// This is a
							// neighbor

							// Record area
					ptr[j]->area = ptr[i]->area;

							// Move to front
							// for next round of
							// processing
					parity_data *tmp = ptr[cur_done+1];
					ptr[cur_done+1] = ptr[j];
					ptr[j] = tmp;
					cur_done++;
				}
			}
		}
	}

	int score = 0;

	if (cur_area == 1) {
		if (DEBUG_PARITY)
			std::cout << "Area=" << cur_area << '\n';
		return score;
	}

	if (DEBUG_PARITY) {
		for (int i = 0; i < num_data; ++i) {
			std::cout << char(data[i].x+'A') << char(data[i].y+'1') 
			     << '-' << data[i].area << ' ';
		}
		std::cout << '\n';
		std::cout << "Area=" << cur_area;
	}

	for (int i = 0; i < NUM_MOVE/4; ++i)
		count[i] = 0;
	for (int i = 0; i < num_data; ++i) {
		count[data[i].area]++;
	}

	int odd_up_for_grab = 0;
	for (int i = 0; i < cur_area; ++i) {
		if (count[i] <= 8) {
			bool black_playable = false;
			bool white_playable = true;

					// Check playable
			for (int j = 0; j < num_data; ++j) {
				if (ptr[j]->area == i
				    && info.board->can_play_nocheck(BLACK,
						xy_to_pos(ptr[j]->x, ptr[j]->y))) {
					black_playable = true;
					break;
				}
			}

			for (int j = 0; j < num_data; ++j) {
				if (ptr[j]->area == i
				    && info.board->can_play_nocheck(WHITE,
						xy_to_pos(ptr[j]->x, ptr[j]->y))) {
					white_playable = true;
					break;
				}
			}

			if (DEBUG_PARITY)
				std::cout << " area" << i << '=' << count[i] 
				     << (black_playable?'B':'-') 
				     << (white_playable?'W':'-');

			if (count[i] == 1) {
					// Hole with 1 empty
				if (black_playable && !white_playable)
					// Free move for black or force white to pass
					score += 8;
				else if (!black_playable && white_playable)
					// Free move for white or force black to pass
					score -= 8;
				else if (black_playable && white_playable)
					odd_up_for_grab++;
			}
			else if (count[i] & 1) {
					// Odd hole
				if (black_playable && !white_playable)
					// Force white to pass
					score += 4;
				else if (!black_playable && white_playable)
					// Force black to pass
					score -= 4;
				else if (black_playable && white_playable)
					odd_up_for_grab++;
			}
			else {		// Even hole
					// Swindle analysis is done via searching
					// since playing swindle hole produces 
					// one-empty hole with +/- 8 score
				if (black_playable && !white_playable)
					// Force white to pass but lose parity
					score += 1;
				else if (!black_playable && white_playable)
					// Force black to pass but lose parity
					score -= 1;
			}
		}
		else {
					// Hole with > 8 empties
			if (count[i] & 1)
				odd_up_for_grab++;
		}
	}

	if (odd_up_for_grab & 1) {
					// Odd number of holes left
					// Next player can take the last move
		if (player == BLACK)
			score += 4;
		else
			score -= 4;
	}
	else {
					// Odd number of holes left
					// Next player can take the last move
		if (player == BLACK)
			score -= 4;
		else
			score += 4;
	}

	if (DEBUG_PARITY)
		std::cout << " odd=" << odd_up_for_grab << " score=" << score << '\n';

	return score;
}

int	parity_eval(byte_board_info *board, int player)
{
	search_info info;
	info.board = board;
	init_endgame_iterator(board, info.empties);
	return parity_eval_alpha_beta(info, player);
}
